package com.hyb.algorithm.data.struct.dp;

/**
 * @author: ybhu
 * @create: 2021/08/28 08:30
 */
public class Kmp {

    public Kmp() {
    }


    public static void main(String[] args) {
        Kmp exe = new Kmp();

        String haystack = "CABAABABC";
        String needle = "ABABC";
        int ret = exe.strStr(haystack, needle);

        System.out.println(ret);
    }

    public int strStr(String haystack, String needle) {

        Kmp exe = new Kmp(needle);

       return exe.search(haystack);
    }

    public int strStr2(String haystack, String needle) {


        int n = haystack.length();
        int m = needle.length();

        if (n == 0 && m == 0) {
            return 0;
        }

        for (int i = 0; i <= n - m; i++) {
            int j = 0;
            for (; j < m; j++) {
                if (haystack.charAt(i + j) != needle.charAt(j)) {
                    break;
                }

                if (j ==m-1) {
                    return i;
                }
            }


        }
        return -1;
    }

    private int[][] dp;
    private String pat;

    public Kmp(String pat) {
        this.pat = pat;
        int M = pat.length();
        // dp[状态][字符] = 下个状态
        dp = new int[M][256];
        // base case
        dp[0][pat.charAt(0)] = 1;
        // 影子状态 X 初始为 0
        int X = 0;
        // 构建状态转移图（稍改的更紧凑了）
        for (int j = 1; j < M; j++) {
            for (int c = 0; c < 256; c++)
                dp[j][c] = dp[X][c];
            dp[j][pat.charAt(j)] = j + 1;
            // 更新影子状态
            X = dp[X][pat.charAt(j)];
        }
    }

    public int search(String txt) {
        int M = pat.length();
        int N = txt.length();
        // pat 的初始态为 0
        int j = 0;
        for (int i = 0; i < N; i++) {
            // 计算 pat 的下一个状态
            j = dp[j][txt.charAt(i)];
            // 到达终止态，返回结果
            if (j == M) return i - M + 1;
        }
        // 没到达终止态，匹配失败
        return -1;
    }

}
